package top.datacluster.basic.algorithm.leetcode.stack;

import java.util.Arrays;
import java.util.Stack;

public class LeetCode503 {

    public int[] nextGreaterElements(int[] nums) {
        Element max = new Element();

        for (int i = 0; i < nums.length; i++){
            if (max.data < nums[i]){
                max.data = nums[i];
                max.index = i;
            }
        }

        int pos[] = new int[nums.length];
        Arrays.fill(pos, -1);

        Stack<Element> stack = new Stack<>();

        Element element = new Element();
        element.data = nums[0];
        element.index = 0;
        stack.push(element);

        for (int i = 1; i < nums.length; i++){
            while (!stack.isEmpty() && stack.peek().data < nums[i]){
                element = stack.pop();
                pos[element.index] = nums[i];
            }
            Element element1 = new Element();
            element1.data = nums[i];
            element1.index = i;
            stack.push(element1);
        }
        if (stack.size() > 1){
            for (int i = 0; i < nums.length; i++){
                while (!stack.isEmpty() && stack.peek().data < nums[i]){
                    element = stack.pop();
                    pos[element.index] = nums[i];
                }
            }
        }
        return pos;

    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{5,4,3,2,1};

        new LeetCode503().nextGreaterElements(nums1);
    }
}

class Element{
    int data;
    int index;
}